#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
#include <stddef.h>
#include <string.h>

#include "abb.h"
#include "nodo_arbol.h"
#include "pila.h"

/************************************************
*	Definicion de los tipos de datos	*
************************************************/

struct nodo_arbol
{
	char *clave;
	void *dato;
	nodo_arbol_t *hijo_izq;
	nodo_arbol_t *hijo_der;
};

struct abb_iter{
    pila_t *pila;
};

/************************************************
*		Primitivas del nodo_arbol	*
************************************************/

nodo_arbol_t *nodo_crear(const char* clave, void* dato)
{
    nodo_arbol_t *nodo = malloc(sizeof(nodo_arbol_t));
	if(!nodo)
        return NULL;

    char *clave_interna = malloc(sizeof(char)*(strlen(clave)+1));
    if(!clave_interna)
    {
        free(nodo);
        return NULL;
    }

    strcpy(clave_interna,clave);

    nodo->clave = clave_interna;

    nodo->hijo_izq = NULL;
    nodo->hijo_der = NULL;

    nodo->dato = dato;

	return nodo;
}

nodo_arbol_t* buscar_nodo_padre(abb_nodo_comparar_clave_t cmp,nodo_arbol_t* padre_anterior,nodo_arbol_t* raiz,nodo_arbol_t* nodo_hijo)
{
	if(raiz != NULL)
	{
		int comp = nodo_comparar(raiz,nodo_hijo,cmp);
		if(comp == 0)	//El nodo buscado existe y el padre es el padre del nodo actual (el mismo)
		{
			return padre_anterior;
		}
		else if(comp > 0)	//El nodo buscado es mas chico que el nodo actual
		{
			if(raiz->hijo_izq != NULL)	//Si existe un hijo mas chico del actual, analizo a partir de este
				return buscar_nodo_padre(cmp,raiz,raiz->hijo_izq,nodo_hijo);
		}
		else		//El nodo buscado seria mas grande que el nodo actual
		{	if(raiz->hijo_der != NULL)	//Si existe un hijo mas grande del actual, analizo a partir de este
				return buscar_nodo_padre(cmp,raiz,raiz->hijo_der,nodo_hijo);
		}
	}//Si el nodo es nulo o no se puede seguir avanzando hacia el lado correcto, el nodo es el padre
	return raiz;
}

nodo_arbol_t* buscar_nodo(abb_nodo_comparar_clave_t cmp,nodo_arbol_t* nodo,const char* clave)
{
	if(nodo != NULL)
	{
		int comp = cmp(nodo->clave,clave);
		if(comp == 0)// Si el nodo actual es el buscado, lo devuelo
		{
			return nodo;
		}
		else if(comp < 0)//Si el nodo actual es menoral buscado, sigo hacia la derecha
		{
			if(nodo->hijo_der == NULL)	//Si no existe hijo derecho, el nodo no pertenece
				return NULL;
			return buscar_nodo(cmp,nodo->hijo_der,clave);
		}
		else		//Si el nodo actual es mayor al buscado, sigo hacia la izquierda
		{
			if(nodo->hijo_izq == NULL)//Si no existe hijo izquierdo, el nodo no pertenece
				return NULL;
			return	buscar_nodo(cmp,nodo->hijo_izq,clave);
		}
	}//Si el nodo pasado es NULL, devuelvo NULL
	return NULL;
}


//Busca el hijo mas a la derecha del pasado
nodo_arbol_t* buscar_maximo(nodo_arbol_t* nodo)
{
	if(nodo->hijo_der != NULL)
		return buscar_maximo(nodo->hijo_der);
	return nodo;
}

//Busca el hijo mas a la izquierda del pasado
nodo_arbol_t* buscar_minimo(nodo_arbol_t* nodo)
{
	if(nodo->hijo_izq != NULL)
		return buscar_minimo(nodo->hijo_izq);
	return nodo;
}

//Devuelve 0 si ambos nodos poseen la misma clave, menor a 0 si nodo2 es mayor a nodo1 y mayor a 0 si nodo1 es mayor a nodo2
int nodo_comparar(nodo_arbol_t* nodo1,nodo_arbol_t* nodo2, abb_nodo_comparar_clave_t cmp)
{
	int comp = cmp(nodo1->clave,nodo2->clave);
	return comp;
}

//Devuelve true si el nodo1 es mayor y falso de no ser asi
bool nodo_es_mayor(nodo_arbol_t* nodo1,nodo_arbol_t* nodo2, abb_nodo_comparar_clave_t cmp)
{
	int comp = nodo_comparar(nodo1,nodo2,cmp);
	if(comp > 0)
		return true;
	return false;
}

bool nodos_ordenados(nodo_arbol_t* nodo, abb_nodo_comparar_clave_t cmp)
{
	bool result = true;
	if(nodo->hijo_izq != NULL)
	{	result &= (cmp(nodo->clave,nodo->hijo_izq->clave) > 0);
		result &= nodos_ordenados(nodo->hijo_izq,cmp);
	}
	if(nodo->hijo_der != NULL)
	{
		result &= (cmp(nodo->clave,nodo->hijo_der->clave) < 0);
		result &= nodos_ordenados(nodo->hijo_der,cmp);
	}
	return result;
}

void intercambiar_nodos(nodo_arbol_t* nodo1, nodo_arbol_t* nodo2)
{
	char* clave_aux = nodo1->clave;
	void* dato_aux  = nodo1->dato;

	nodo1->clave = nodo2->clave;
	nodo1->dato = nodo2->dato;

	nodo2->clave = clave_aux;
	nodo2->dato  = dato_aux;
}

/***********************************************************
	ACCESO/ESCRITURA A DATOS DEL NODO
***********************************************************/

void nodo_agregar_dato(nodo_arbol_t* nodo,void* dato,abb_nodo_destruir_dato_t destruir_dato)
{
	if(destruir_dato != NULL)
	{	destruir_dato(nodo->dato);	}
	nodo->dato = dato;
}

void* nodo_ver_dato(nodo_arbol_t* nodo)
{	return nodo->dato;	}

nodo_arbol_t* nodo_ver_hijo_izq(nodo_arbol_t* nodo)
{	return nodo->hijo_izq;	}

nodo_arbol_t* nodo_ver_hijo_der(nodo_arbol_t* nodo)
{	return nodo->hijo_der;	}

void nodo_agregar_hijo_izq(nodo_arbol_t* nodo,nodo_arbol_t* nodo_hijo)
{	nodo->hijo_izq = nodo_hijo;	}

void nodo_agregar_hijo_der(nodo_arbol_t* nodo,nodo_arbol_t* nodo_hijo)
{	nodo->hijo_der = nodo_hijo;	}

bool nodo_tiene_hijos(nodo_arbol_t* nodo)
{	return (nodo->hijo_der != NULL || nodo->hijo_izq != NULL);	}

/**********************************************************
			DESTRUCTOR
**********************************************************/
void nodo_destruir_sin_dato(nodo_arbol_t* nodo)
{
	free(nodo->clave);
	free(nodo);
}

void nodo_destruir(nodo_arbol_t* nodo, abb_nodo_destruir_dato_t destruir_dato)
{
	if(destruir_dato != NULL)
	{	destruir_dato(nodo->dato);	}
	free(nodo->clave);
	free(nodo);
}

void nodo_destruir_en_cadena(nodo_arbol_t* nodo,abb_nodo_destruir_dato_t destruir_dato)
{
	if(nodo->hijo_izq != NULL)
	{	nodo_destruir_en_cadena(nodo->hijo_izq,destruir_dato);}

	if(nodo->hijo_der != NULL)
		nodo_destruir_en_cadena(nodo->hijo_der,destruir_dato);

	nodo_destruir(nodo,destruir_dato);
}

/**********************************************************
            UTILES
**********************************************************/

void in_orden(nodo_arbol_t *nodo, bool visitar(const char *, void *, void *),void *extra)
{
    if(nodo)
    {
        in_orden(nodo->hijo_izq,visitar,extra);
        if(!visitar(nodo->clave,nodo->dato,extra))
            return;

        in_orden(nodo->hijo_der,visitar, extra);
    }
}

void nodo_cargar_iter(abb_iter_t *iter,nodo_arbol_t *nodo)
{
    if(!nodo)
        return;

    pila_apilar(iter->pila,nodo);

    nodo_cargar_iter(iter,nodo->hijo_izq);

    return;
}

abb_iter_t *nodo_iter_in_crear(nodo_arbol_t *raiz)
{
    abb_iter_t *iter = malloc(sizeof(abb_iter_t));

    if(!iter)
        return NULL;

    iter->pila = pila_crear();

    if(!iter->pila)
    {
        free(iter);
        return NULL;
    }

    nodo_cargar_iter(iter,raiz);

    return iter;
}

void nodo_iter_in_destruir(abb_iter_t *iter)
{
    pila_destruir(iter->pila);
    free(iter);
}

const char *nodo_iter_ver_actual(const abb_iter_t *iter)
{
    if(pila_esta_vacia(iter->pila))
        return NULL;

    const nodo_arbol_t *nodo = pila_ver_tope(iter->pila);
    return nodo->clave;
}

bool nodo_iter_al_final(const abb_iter_t *iter)
{
    return pila_esta_vacia(iter->pila);
}

bool nodo_iter_avanzar(abb_iter_t *iter)
{
    	nodo_arbol_t *nodo = pila_desapilar(iter->pila);

    	if(!nodo)
    	{
		return false;
    	}
	else
	{	nodo_cargar_iter(iter,nodo->hijo_der);
    		return true;
	}
}
